package com.zklh.leetcode.constructor.lru;

import com.zklh.leetcode.tree.model.TreeNode;

import java.util.HashMap;

/**
 * 最近最少使用算法实现, 自定义数据结构
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/6/13 10:12
 */
public class LRUCacheImplV1 implements LRU{

    private DoubleList cache;

    private HashMap<Integer, Node> map;

    private int capacity;


    public LRUCacheImplV1(int capacity) {
        this.capacity = capacity;
        cache = new DoubleList();
        map = new HashMap<>();
    }

    @Override
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        makeRecently(key);
        return node.val;
    }

    @Override
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = val;
            makeRecently(key);
            return;
        }

        if (cache.getSize() == capacity) {
            removeLeastRecently();
        }
        addRecently(key, val);
    }



    private void makeRecently(int key) {
        Node node = map.get(key);
        cache.remove(node);
        cache.addFirst(node);
    }


    private void addRecently(int key, int val){
        Node node = new Node(key,val);
        cache.addFirst(node);
        map.put(key,node);
    }

    private void removeLeastRecently(){
        Node removedNode=cache.removeLast();
        map.remove(removedNode.key);
    }

    @Override
    public String toString() {
        return cache.toString();
    }

    public static void main(String[] args) {
        LRU lru = new LRUCacheImplV1(2);
        lru.put(1,1);

        lru.put(2,2);

        int i = lru.get(1);

        lru.put(3,3);
        int i2 = lru.get(2);
        lru.put(1,4);

    }

}
